// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/

// 算法思路总结：
// 1. 使用贪心策略求解股票买卖最大利润
// 2. 维护历史最低价格，计算当前价格与最低价的差值
// 3. 遇到更低价格更新最低价，否则更新最大利润
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int maxProfit(vector<int>& prices) 
    {
        int m = prices.size();
        if (m <= 1) return 0;

        int minVal = prices[0], ret = 0;
        for (int i = 1 ; i < m ; i++)
        {
            if (prices[i] >= minVal)
                ret = max(ret, prices[i] - minVal);
            else 
                minVal = prices[i];
        }

        return ret;
    }
};

int main()
{
    vector<int> v1 = {7,1,5,3,6,4}, v2 = {7,6,4,3,1};
    Solution sol;

    cout << sol.maxProfit(v1) << endl;
    cout << sol.maxProfit(v2) << endl;

    return 0;
}